package com.niuke;

import com.pojo.ListNode;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-12-09 18:08:40
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-12-09     张李鑫                     1.0         1.0 Version
 */
public class JZ25 {

    /**
     * 输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
     * 数据范围： 0 \le n \le 10000≤n≤1000，-1000 \le 节点值 \le 1000−1000≤节点值≤1000
     * 要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
     *
     * @param list1
     * @param list2
     * @return
     */
    public ListNode Merge(ListNode list1, ListNode list2) {
        if (list1==null&&list2==null){
            return null;
        }
        if (list1==null){
            return list2;
        }
        if (list2==null){
            return list1;
        }
        ListNode cur = null;
        if (list1.val > list2.val) {
            cur = list2;
            list2 = list2.next;
        } else {
            cur = list1;
            list1 = list1.next;
        }
        ListNode loop=cur;

        while (list1 != null && list2 != null) {
            if (list1.val > list2.val) {
                loop.next = list2;
                list2 = list2.next;
            } else {
                loop.next = list1;
                list1 = list1.next;
            }
            loop = loop.next;
        }
        loop.next=list1==null?list2:list1;
        return cur;
    }



}
